package _11_整理题目._2_二叉树_递归_dfs_bfs._dfs_路径和;


import org.junit.Test;
import util.TreeNode;


/**
 * https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
 *
 * 给定一个仅包含数字 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
 * 例如根节点到叶子节点的一条路径是 1 2 3 ,那么这条路径就用 123 来代替。
 * 找出根节点到叶子节点的所有路径表示的数字之和
 *
 *      计算当前值 的时候可以采用  sum * 10 + root.val
 *                      或采用  sb.append , 然后 Integer.parseInt(sb.toString())
 */
public class _063_二叉树根节点到叶子节点的所有路径和 {
    
    private int total = 0;
    
    public int sumNumbers (TreeNode root) {
        dfs(root, 0);
        return total;
    }
    
    private void dfs(TreeNode root, int sum) {
        if (root == null) return;

        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            total += sum;
        }

        dfs(root.left, sum);
        dfs(root.right, sum);
    }
    
    @Test
    public void main() {
        Integer[] input = {1, 2, 3}; // 25
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(sumNumbers(root));
    }


    private int result = 0;
    StringBuilder sb = new StringBuilder();

    public int sumNumbers1(TreeNode root) {
        dfs1(root);
        return result;
    }

    public void dfs1(TreeNode root) {
        if(root==null) return;

        sb.append(root.val);
        if(root.left==null && root.right==null) {
            result += Integer.parseInt(sb.toString());
        }

        dfs1(root.left);
        dfs1(root.right);

        sb.deleteCharAt(sb.length()-1);
    }
}
